package class07;

public class Code07_MinPathSum {
    // 时间空间复杂度都是O(M*N) MN 为dp 矩阵大小
    static int minPathSum1(int[][] m) {
        // 非空检验

        int row = m.length;
        int col = m[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = m[0][0];
        for (int i = 1; i < col; i++) {
            dp[0][i] = dp[0][i - 1] + m[0][i];
        }

        for (int j = 1; j < row; j++) {
            dp[j][0] = dp[j - 1][0] + m[j][0];
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + m[i][j];
            }
        }
        return dp[row - 1][col - 1];
    }
    //   利用滚动数组压榨空间，但是过程不可回溯
    static int minPathSum2(int[][] m) {
        int more = Math.max(m.length, m[0].length);
        int less = Math.min(m.length, m[0].length);
        boolean rowmore = more == m.length; // 行数是否等于列数

        int[] helpArr = new int[less];
        helpArr[0] = m[0][0];
        for (int i = 1; i < less; i++) {
            helpArr[i] = helpArr[i - 1] + (rowmore ? m[0][i] : m[i][0]);
        }

        for (int i = 1; i < more; i++) {
            helpArr[0] = helpArr[0] + (rowmore ? m[i][0] : m[0][i]);
            for (int j = 1; j < less; j++) {
                helpArr[j] = Math.min(helpArr[j - 1], helpArr[j]) + (rowmore ? m[i][j] : m[j][i]);
            }
        }
        return helpArr[less - 1];
    }

    public static void main(String[] args) {
        int[][] m = {{1, 3, 5, 9}, {8, 1, 3, 4}, {5, 0, 6, 1}, {8, 8, 4, 0}};
        System.out.println(minPathSum1(m));
        System.out.println(minPathSum2(m));
    }
}
